//
// Created by 张朝辉 on 23-9-13.
//

#include <iostream>
#include <queue>
#include "dfa.h"
// 构造函数
DFA::DFA(std::set<std::string> state_set, std::set<char> char_set, std::string start_state, std::set<std::string> final_set,
         std::map<std::pair<std::string, char>, std::string> rule_table)
         :state_set(state_set),char_set(char_set),start_state(start_state),final_set(final_set),rule_table(rule_table){}

/*
 * 状态转换函数
 * now_state: 当前状态，now_char: 接收符号
 */
auto DFA::state_transition(std::string now_state, char now_char) -> std::string {
    // 从状态转换表中查找转换后的状态
    auto it = rule_table.find(std::make_pair(now_state, now_char));
    // 若能查找到转换后的状态则返回，否则抛出异常
    if(it != rule_table.end()){
        return it->second;
    }else{
        throw "状态转换出错";
    }
}

/*
 * 扩展状态转换函数
 * now_state: 当前的状态，w: 接收的串
 */
auto DFA::extend_state_transition(std::string now_state, std::string w) -> std::string{
    // 若接收的串为空串，则返回当前状态，否则执行递归函数
    if(w.length() == 0)return now_state;
    return state_transition(extend_state_transition(now_state,w.substr(0,w.length()-1)),w[w.length()-1]);
}

/*
 * 判断某个字符串能否被此DFA正确识别
 */
auto DFA::isAccept_str(std::string str) -> bool {
    std::string res = extend_state_transition(start_state,str);
    if(final_set.find(res) != final_set.end()){
        return true;
    }
    return false;
}

/*
 * 将一个DFA转换为正则表达式
 */
auto DFA::DFA2Regex() -> std::string {
    resetRuleTable();
    std::string res;
    for(auto &fin: final_set){
        if(res.empty()){
            res = Regex(std::stoi(start_state),std::stoi(fin),std::stoi(fin));
        }else{
            res.append("+"+Regex(std::stoi(start_state),std::stoi(fin),std::stoi(fin)));
        }
    }
    return res;
}

/*
 * 递归构造正则表达式
 */
auto DFA::Regex(int i, int j, int k) -> std::string {
    if(k == 0){
        return regexZero(i,j);
    }
    return "("+Regex(i,j,k-1)+"+"+ Regex(i,k,k-1)+"."+Regex(k,k,k-1)+"*."+Regex(k,j,k-1)+")";
}

/*
 * 重新对DFA中的各个状态进行编号
 */
auto DFA::resetRuleTable() -> void {
    std::map<std::pair<std::string,char>,std::string> newRuleTable;      // 使用新定义的规则表进行替换
    std::set<std::string> newStateSet;           // 新的状态集
    std::set<std::string> newFinalSet;           // 新的终态集
    std::queue<std::string> stateQueue;          //状态队列
    std::map<std::string,std::string> stateMap;        // 新的状态表示和老状态表示的映射
    stateQueue.push(start_state);      // 初始化状态队列
    int stateNum = 1;
    std::string oldState,newState;
    while(!stateQueue.empty()){
        oldState = stateQueue.front();
        stateQueue.pop();
        newState = std::to_string(stateNum++);
        stateMap[oldState] = newState;
        newStateSet.insert(newState);
        if(final_set.find(oldState) != final_set.end()){
            newFinalSet.insert(newState);
        }
        for(auto &nextState: getNextStateSet(oldState)){
            if(stateMap.find(nextState) == stateMap.end()){         // 如果不存在映射关系，则说明需要设置新的状态
                stateQueue.push(nextState);
            }
        }
    }
    // 设置新的规则表
    std::string newFrom,newTo;
    for(auto &r: rule_table){
        newFrom = stateMap.find(r.first.first)->second;
        newTo = stateMap.find(r.second)->second;
        newRuleTable[std::make_pair(newFrom,r.first.second)] = newTo;
    }
    // 使用新的状态转换表进行替换
    rule_table = newRuleTable;
    start_state = std::to_string(1);
    state_set = newStateSet;
    final_set = newFinalSet;
}

/*
 * 获取当前状态经过一次状态转换能达到的所有状态的集合
 */
auto DFA::getNextStateSet(std::string nowState) -> std::set<std::string> {
    std::set<std::string> res{};
    for(auto &it: rule_table){
        if(it.first.first == nowState){
            res.insert(it.second);
        }
    }
    return res;
}

/*
 * 状态i在不经过中间状态的情况下能否转换为状态j，返回状态i到状态j所识别的正则表达式
 */
auto DFA::regexZero(int i, int j) -> std::string{
    std::string res;
    for(auto &r: rule_table){
        if(r.first.first == std::to_string(i) && r.second == std::to_string(j)){
            std::string s(1,r.first.second);
            if(res.empty()){
                res = s;
            }else{
                res.append("+"+s);
            }
        }
    }
    if(i == j){
        if(res.empty()){
            res.append("ε");
        } else{
            res.append("+ε");
        }
    }
    if(res.empty()) { res.append("Φ"); }
    return (res == "ε" || res == "Φ" || res.length() == 1)?res:"("+res+")";
}

/*
 * 打印DFA的相关信息
 */
auto DFA::description() -> void {
    std::cout<<"--------------------------------------当前DFA详情----------------------------------------"<<std::endl;
    std::cout<<"状态集：{ ";
    for(auto &s: state_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"字符集：{ ";
    for(auto &s: char_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"开始状态："<<start_state<<std::endl;
    std::cout<<"接受状态集：{ ";
    for(auto &s: final_set){
        std::cout<<s<<" ";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"状态转换表：{ ";
    for(auto &r: rule_table){
        std::cout<<"δ("<<r.first.first<<","<<r.first.second<<") = "<<r.second<<"\t";
    }
    std::cout<<"}"<<std::endl;
    std::cout<<"----------------------------------------------------------------------------------------"<<std::endl;
}
